package leetcode_401_500;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class LeeCode_494 {
    public static void main(String[] args) {
//        System.out.println(findTargetSumWays(new int[]{1, 1, 1, 1, 1}, 3));
//        System.out.println(findTargetSumWays(new int[]{1}, 1));
//        System.out.println(findTargetSumWays(new int[]{1, 0}, 1));
//        System.out.println(findTargetSumWays(new int[]{0,0,0,0,0,0,0,0,1}, 1));
//        System.out.println(findTargetSumWays(new int[]{0,0,0,0,0,0,0,0,1}, 1));
//        System.out.println(findTargetSumWays(new int[]{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 1));
        System.out.println(findTargetSumWays(new int[]{0,0,0,0,0,0,0,1000}, 1000));
    }
    private static int findTargetSumWays(int[] nums, int target) {
        if (target < 0)
            target = -target;
        int s = 0;
        Arrays.sort(nums);
        if (nums[nums.length - 1] == 0){
            return 1 << nums.length;
        }
        for (int num : nums) {
            s += num;
        }
        if ((s + target) % 2 != 0)
            return 0;
        int p = (s + target) / 2;

        Set<Integer> used = new HashSet<>();
        dfs(0, nums, 0, p, 0, used);
        return used.size();
    }
    private static void dfs(int status, int [] nums, int i, int target, int sum, Set<Integer> used){
        if (target == sum){
            used.add(status);
            return;
        }
        if (sum > target || i >= nums.length) {
            return;
        }
        dfs(status | (1 << i), nums, i + 1, target, sum + nums[i], used);
        dfs(status, nums, i + 1, target, sum, used);
    }
}
